package com.huanf;

import org.junit.jupiter.api.Test;
import java.text.DecimalFormat;
import java.util.Arrays;

public class Demo1 {

    //---------------------------------二分查找--------------------------------------

    /**
     * 二分查找，也称为折半查找，它要求数据集合必须是有序的，它的基本思想是将数据集合分成两半，
     * 如果目标元素比中间元素小，就在前半部分继续查找，否则在后半部分继续查找，直到找到目标元素或数据集合为空。二分查找的时间复杂度为O(logn)
     * 查找某个数在数组的哪个位置
     * int[] arr: 数据源
     * int num: 要找的数
     */
    @Test
    void binarySearchTest() {
        int[] arr ={1, 3, 5, 7, 9, 11, 13};
        int target = 11;
        long startTime = System.nanoTime();
        Integer result = binarySearch(arr, target);
        long endTime = System.nanoTime();
        double totalTime = (endTime - startTime) / 1000000000.0;
        String useTime = new DecimalFormat("#.#########").format(totalTime);
        System.out.println("你要找的元素在: " + result + "索引所在的位置，耗费时间是: " + useTime + " 秒");
    }

    private int binarySearch(int[] arr, int num) {
        int min = 0;
        int max = arr.length - 1;
        while (true) {
            if (min > max) {
                return -1;
            }
            int mid = (min + max) / 2;
            if (arr[mid] > num) {
                max = mid - 1;
            } else if (arr[mid] < num) {
                min = mid + 1;
            } else {
                return mid;
            }
        }
    }

    //---------------------------------线性查找--------------------------------------
    /**
     * 线性查找是最简单的查找算法之一，它的基本思想是从数据集合的第一个元素开始逐个比较，
     * 直到找到目标元素或遍历完整个数据集合。线性查找的时间复杂度为O(n)
     * 查找某个数在数组的哪个位置
     * int[] arr: 数据源
     * int num: 要找的数
     */
    @Test
    void linearSearchTest() {
        int[] arr ={1, 3, 5, 7, 9, 11, 13};
        int target = 11;
        long startTime = System.nanoTime();
        Integer result = linearSearch(arr, target);
        long endTime = System.nanoTime();
        double totalTime = (endTime - startTime) / 1000000000.0;
        String useTime = new DecimalFormat("#.#########").format(totalTime);
        System.out.println("你要找的元素在: " + result + "索引所在的位置，耗费时间是: " + useTime + " 秒");
    }

    private int linearSearch(int[] arr, int num) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == num) {
                return i;
            }
        }
        throw new RuntimeException("未找到");
    }



    //---------------------------------冒泡排序--------------------------------------

    /**
     * 将相邻的两个元素进行比较，如果顺序不对就交换它们的位置。该算法的时间复杂度为O(n^2)
     * 把数组里面的元素进行升序、降序排序
     * int[] arr: 数据源
     */
    @Test
    void bubbleSortTest() {
        int arr[]  = {1, 5, 0, -3, -5, 5, 0, 8, 4, 2};
        long startTime = System.nanoTime(); // 记录排序结束时间，纳秒
        int[] result = bubbleSort(arr);
        long endTime = System.nanoTime(); // 记录排序结束时间，纳秒
        double totalTime = (endTime - startTime) / 1000000000.0;
        String useTime = new DecimalFormat("#.#########").format(totalTime);
        System.out.println("排序完成: " + Arrays.toString(result) + "，耗费时间是: " + useTime + " 秒");
    }

    private int[] bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) { //大于号表示升序，小于号表示降序
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        return arr;
    }

    //---------------------------------选择排序--------------------------------------

    /**
     * 每次选择未排序序列中最小的元素，将其放到已排序序列的末尾。该算法的时间复杂度也为O(n^2)
     * 把数组里面的元素进行升序、降序排序
     * int[] arr: 数据源
     */
    @Test
    void chooseSort() {
        int arr[] = {1, 5, 0, -3, -5, 5, 0, 8, 4, 2};
        long startTime = System.nanoTime();
        int[] result = chooseSort(arr);
        long endTime = System.nanoTime();
        double totalTime = (endTime - startTime) / 1000000000.0;
        String useTime = new DecimalFormat("#.#########").format(totalTime);
        System.out.println("排序完成: " + Arrays.toString(result) + "，耗费时间是: " + useTime + " 秒");
    }

    private int[] chooseSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) { //大于号表示升序，小于号表示降序
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }

    //---------------------------------插入排序--------------------------------------

    /**
     * 将未排序序列中的每个元素插入到已排序序列的合适位置。该算法的时间复杂度也为O(n^2)
     * 把数组里面的元素进行升序、降序排序
     * int[] arr 数据源
     */
    @Test
    void insertionSortTest() {
        int arr[] = {1, 5, 0, -3, -5, 5, 0, 8, 4, 2};
        long startTime = System.nanoTime();
        int[] result = insertionSort(arr);
        long endTime = System.nanoTime();
        double totalTime = (endTime - startTime) / 1000000000.0;
        String useTime = new DecimalFormat("#.#########").format(totalTime);
        System.out.println("排序完成: " + Arrays.toString(result) + "，耗费时间是: " + useTime + " 秒");
    }

    private int[] insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];
            int index = i - 1;
            while (index >= 0 && insertVal < arr[index]) { //第二个，小于号表示升序，大于号表示降序
                arr[index + 1] = arr[index];
                index--;
            }
            arr[index + 1] = insertVal;
        }
        return arr;
    }

    //---------------------------------快速排序--------------------------------------

    /**
     * 选择一个基准元素，将序列分成两部分，一部分元素比基准元素小，一部分元素比基准元素大，
     * 然后分别对这两部分进行快速排序。该算法的时间复杂度为O(nlogn)
     * 把数组里面的元素进行升序、降序排序
     * int[] arr: 数据源
     * int start: 哪个位置后面的元素需要排序
     * int end: 排序截止到哪个位置的元素
     */
    @Test
    void quickSortTest() {
        int arr[] = {1, 5, 0, -3, -5, 5, 0, 8, 4, 2};
        long startTime = System.nanoTime();
        int[] result = quickSort(arr, 0, arr.length - 1);
        long endTime = System.nanoTime();
        double totalTime = (endTime - startTime) / 1000000000.0;
        String useTime = new DecimalFormat("#.#########").format(totalTime);
        System.out.println("排序完成: " + Arrays.toString(result) + "，耗费时间是: " + useTime + " 秒");
    }


    private int[] quickSort(int arr[], int start, int end) {
        int pivot = arr[start];
        int i = start;
        int j = end;
        while (i < j) {
            while ((i < j) && (arr[j] > pivot)) { //第二个，大于号表示升序，小于号表示降序
                j--;
            }
            while ((i < j) && (arr[i] < pivot)) {//第二个，小于号表示升序，大于号表示降序
                i++;
            }
            if ((arr[i] == arr[j]) && (i < j)) {
                i++;
            } else {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        if (i - 1 > start) {
            arr = quickSort(arr, start, i - 1);
        }
        if (j + 1 < end) {
            arr = quickSort(arr, j + 1, end);
        }
        return (arr);
    }

    //---------------------------------希尔排序--------------------------------------

    /**
     * 把数组里面的元素进行升序、降序排序
     * int[] arr: 数据源
     */
    @Test
    void shellSortTest() {
        int arr[] = {1, 5, 0, -3, -5, 5, 0, 8, 4, 2};
        long startTime = System.nanoTime();
        int[] result = shellSort(arr);
        long endTime = System.nanoTime();
        double totalTime = (endTime - startTime) / 1000000000.0;
        String useTime = new DecimalFormat("#.#########").format(totalTime);
        System.out.println("排序完成: " + Arrays.toString(result) + "，耗费时间是: " + useTime + " 秒");
    }

    private int[] shellSort(int[] arr) {
        int dk = arr.length / 2;
        while (dk >= 1) {
            for (int i = dk; i < arr.length; i++) {
                if (arr[i] < arr[i - dk]) { //小于号表示升序，大于号表示降序
                    int j;
                    int x = arr[i];
                    arr[i] = arr[i - dk];
                    for (j = i - dk; j >= 0 && x < arr[j]; j = j - dk) { //第二个，小于号表示升序，大于号表示降序
                        arr[j + dk] = arr[j];
                    }
                    arr[j + dk] = x;
                }
            }
            dk = dk / 2;
        }
        return arr;
    }

    //---------------------------------归并排序--------------------------------------

    /**
     * 把数组里面的元素进行升序、降序排序
     * int[] arr: 数据源
     */
    @Test
    void mergeSortTest() {
        int arr[] = {1, 5, 0, -3, -5, 5, 0, 8, 4, 2};
        long startTime = System.nanoTime();
        int[] result = mergeSort(arr, 0, arr.length - 1);
        long endTime = System.nanoTime();
        double totalTime = (endTime - startTime) / 1000000000.0;
        String useTime = new DecimalFormat("#.#########").format(totalTime);
        System.out.println("排序完成: " + Arrays.toString(result) + "，耗费时间是: " + useTime + " 秒");
    }

    private int[] mergeSort(int[] nums, int l, int h) {
        if (l == h) {
            return new int[]{nums[l]};
        }
        int mid = l + (h - l) / 2;
        int[] leftArr = mergeSort(nums, l, mid);
        int[] rightArr = mergeSort(nums, mid + 1, h);
        int[] newNum = new int[leftArr.length + rightArr.length];

        int m = 0, i = 0, j = 0;
        while (i < leftArr.length && j < rightArr.length) {
            newNum[m++] = leftArr[i] <= rightArr[j] ? leftArr[i++] : rightArr[j++]; //小于等于表示升序，大于等于表示降序
        }
        while (i < leftArr.length) {
            newNum[m++] = leftArr[i++];
        }
        while (j < rightArr.length) {
            newNum[m++] = rightArr[j++];
        }
        return newNum;
    }

    //----------------------------------堆排序--------------------------------------

    /**
     * 把数组里面的元素进行升序、降序排序
     * int[] arr: 数据源
     */
    @Test
    void heapSortTest() {
        int arr[] = {1, 5, 0, -3, -5, 5, 0, 8, 4, 2};
        long startTime = System.nanoTime();
        int[] result = heapSort(arr);
        long endTime = System.nanoTime();
        double totalTime = (endTime - startTime) / 1000000000.0;
        String useTime = new DecimalFormat("#.#########").format(totalTime);
        System.out.println("排序完成: " + Arrays.toString(result) + "，耗费时间是: " + useTime + " 秒");
    }

    private int[] heapSort(int[] arr){
        int n = arr.length;
        for(int i = n/2 - 1; i >= 0; i--){
            heapify(arr, n, i);
        }
        for(int i = n - 1; i > 0; i--){
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
        return arr;
    }
    private void heapify(int[] arr, int n, int i){
        int largest = i;
        int left = i*2 + 1;
        int right = left + 1;
        if(left < n && arr[left] > arr[largest]){ //第二个，大于表示升序，小于等于表示降序
            largest = left;
        }
        if(right < n && arr[right] > arr[largest]){ //第二个，大于表示升序，小于等于表示降序
            largest = right;
        }
        if(i != largest){
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }

    //----------------------------------桶排序--------------------------------------

    /**
     * 把数组里面的元素进行升序、降序排序
     * int[] arr: 数据源，不能包含负数
     */
    @Test
    void bucketSortTest() {
        int arr[] = {1, 5, 0, 5, 0, 8, 4, 2};
        long startTime = System.nanoTime();
        int[] result = bucketSort(arr);
        long endTime = System.nanoTime();
        double totalTime = (endTime - startTime) / 1000000000.0;
        String useTime = new DecimalFormat("#.#########").format(totalTime);
        System.out.println("排序完成: " + Arrays.toString(result) + "，耗费时间是: " + useTime + " 秒");
    }

    private int[] bucketSort(int[] arr){
        int n = arr.length;
        int bask[][] = new int[10][n];
        int index[] = new int[10];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            max = Math.max(max, (Integer.toString(arr[i]).length()));
        }
        String str;
        for (int i = max - 1; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                str = "";
                if (Integer.toString(arr[j]).length() < max) {
                    for (int k = 0; k < max - Integer.toString(arr[j]).length(); k++)
                        str += "0";
                }
                str += Integer.toString(arr[j]);
                bask[str.charAt(i) - '0'][index[str.charAt(i) - '0']++] = arr[j];
            }
            int pos = 0;
            for (int j = 0; j < 10; j++) { //写成(int j = 9; j >= 0; j--)表示降序
                for (int k = 0; k < index[j]; k++) {
                    arr[pos++] = bask[j][k];
                }
            }
            for (int x = 0; x < 10; x++) {
                index[x] = 0;
            }
        }
        return arr;
    }

    //---------------------------------基数排序--------------------------------------

    /**
     * 把数组里面的元素进行升序、降序排序
     * int[] arr: 数据源，不能包含负数
     */
    @Test
    void baseSortTest() {
        int arr[] = {1, 1210, 5, 0, 82, 124, 5, 0, 8, 4, 2};
        long startTime = System.nanoTime();
        int[] result = baseSort(arr,10);
        long endTime = System.nanoTime();
        double totalTime = (endTime - startTime) / 1000000000.0;
        String useTime = new DecimalFormat("#.#########").format(totalTime);
        System.out.println("排序完成: " + Arrays.toString(result) + "，耗费时间是: " + useTime + " 秒");
    }

    public int[] baseSort(int[] arr, int d) {
        int k = 0;
        int n = 1;
        int m = 1;
        int[][] temp = new int[10][arr.length];
        int[] order = new int[10];
        while (m <= d) {
            for (int i = 0; i < arr.length; i++) {
                int lsd = ((arr[i] / n) % 10);
                temp[lsd][order[lsd]] = arr[i];
                order[lsd]++;
            }
            for (int i = 0; i < 10; i++) { //写成(int i = 9; i >= 0; i--)表示降序
                if (order[i] != 0) {
                    for (int j = 0; j < order[i]; j++) {
                        arr[k] = temp[i][j];
                        k++;
                    }
                }
                order[i] = 0;
            }
            n *= 10;
            k = 0;
            m++;
        }
        return arr;
    }

}